package com.xgb.array;

/**
 * 数据结构：单链表
 * @author barrysandy
 *
 * @param <T>
 */
public class LinkedList<T> {
	
	Node head = new Node(null);
	int size = 0;
	
	/**
	 * 获取元素
	 * @param i
	 * @return
	 */
	public T get(int i) {
		if(i < 0 || i > size - 1) {
			throw new ArrayIndexOutOfBoundsException();
		}else {
			//单链表遍历从头节点开始
			Node temp = head;
			//counter用来计数，找到i在链表里的节点位置，头结点不算链表的真实节点，所以从-1计数
			int counter = -1;
			while(temp != null) {
				if(counter == i) {
					return (T) temp.t;
				}else {
					temp = temp.next;
					counter++;
				}
			}
		}
		
		return null;
		
	}
	
	/**
	 * 添加元素
	 * @param t
	 */
	public void add(T t) {
		Node temp = head;
		//如果下一个节点不为空，则需要继续遍历下一个节点，直到为空时才将数据t插入在该位置
		while(temp.next != null) {
			temp = temp.next;
		}
		temp.next = new Node(t);
		size++;
	}
	
	/**
	 * 指定位置插入
	 * @param i
	 * @param t
	 */
	public void add(int i ,T t) {
		if(i < 0 || i > size - 1) {
			throw new ArrayIndexOutOfBoundsException();
		}else {
			Node temp = head;
			int counter = -1;
			while(temp != null) {
				if((i -1 ) == counter) {
					//将i前面的节点指向新节点node，将新节点node的next指向i节点
					Node node = new Node(t);
					Node back = temp.next;
					temp.next = node;
					node.next = back;
					size++;
				}
				temp = temp.next;
				counter++;
			}
		}
	}
	
	/**
	 * 删除节点
	 * @param i
	 */
	public void delete(int i) {
		if(i < 0 || i > size - 1) {
			throw new ArrayIndexOutOfBoundsException();
		}else {
			Node temp = head;
			int counter = -1;
			while(temp != null) {
				if((i -1 ) == counter) {
					//将i前面的节点指向i后面的节点
					temp.next = temp.next.next;
					size--;
				}
				counter++;
				temp = temp.next;
			}
		}
	}
	
	class Node<T> {
		Node next;
		T t;
		
		Node (T t){
			this.t = t;
		}
	}

	public static void main(String[] args) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		list.add(3,5);
		System.out.println("获取节点 3：" + list.get(3));
	}

}
